package algorithm.leetcode;

public class LeetCode_1370_sortString {

    public String sortString(String s) {
        if (s == null || s.length() <= 1) return s;

        // 26个字母桶，统计词频
        int[] countMap = new int[26];
        for (int i = 0; i < s.length(); i++) {
            countMap[s.charAt(i) - 'a']++;
        }

        StringBuilder ans = new StringBuilder();
        boolean fromSmallToLarge = true; // 是否上升序

        while (ans.length() < s.length()) { // 结果串ans不满，表示还有字符时，持续循环
            if (fromSmallToLarge) { // 如果是上升序，字母桶从小到大
                for (int i = 0; i < 26; i++) {
                    if (countMap[i] > 0) {
                        ans.append((char) ('a' + i)); // 转成char
                        countMap[i]--;
                    }
                }
            } else { // 如果是下降序，字母桶从大到小
                for (int i = 25; i >= 0; i--) {
                    if (countMap[i] > 0) {
                        ans.append((char) ('a' + i));
                        countMap[i]--;
                    }
                }
            }
            fromSmallToLarge = !fromSmallToLarge;
        }

        return ans.toString();
    }

    public static void main(String[] args) {

    }
}
